// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem560.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=560 lang=cpp
 *
 * [560] 和为 K 的子数组
 *
 * https://leetcode-cn.com/problems/subarray-sum-equals-k/description/
 *
 * algorithms
 * Medium (44.86%)
 * Likes:    1394
 * Dislikes: 0
 * Total Accepted:    205.5K
 * Total Submissions: 457.7K
 * Testcase Example:  '[1,1,1]\n2'
 *
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= nums.length <= 2 * 10^4
 * -1000 <= nums[i] <= 1000
 * -10^7 <= k <= 10^7
 * 
 * 
 */

// @lc code=start
#include<vector>
#include<iostream>
#include<unordered_map>
using namespace std;
// 此方法超时
/* class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        vector<int> sumvec;
        int ans=0,sum=0;
        int n=nums.size();
        sumvec.push_back(0);
        for(int i=0;i<n;++i){
            sum+=nums[i];
            sumvec.push_back(sum);
        }
        for(int left=1;left<=n;++left){
            for(int right=left;right<=n;++right){
                if(sumvec[right]-sumvec[left-1]==k){
                    ++ans;
                }
            }
        }
        return ans;
    }
}; */
class Solution{
    public:
    int subarraySum(vector<int>& nums,int k){
        int count=0,psum=0;
        // 键为前缀和psum，值为前缀和出现的次数
        unordered_map<int,int> hashmap;
        hashmap[0]=1;
        for(int i:nums){
            psum+=i;
            // psum由两部分组成，更小的前缀和+k，因此只要查找更小的前缀和个数即可，得到的满足条件
            // 区间是以当前元素i结尾的，保证不会重复
            count+=hashmap[psum-k];
            ++hashmap[psum];
        }
        return count;
    }
};
// @lc code=end

